// 步骤
// 1. 使用cur指针遍历链表，获取节点值位数最长的位数size
// 2. 从个位到高位遍历位数，因为0-9，10个数字，建立10个桶
// 3. 以每个节点对应位数的数字作为索引，将节点值放到对应桶中
// 4. 建立一个哑结点，作为链表的头节点，并使用cur指针指向哑结点
// 5. 将桶中元素依次取出，并根据元素值建立链表节点，并插入到链表后面，从而生成新的链表
// 6. 之后依次十位，高位，值作为索引，放到对应桶中
// 7. 将哑结点的下一个链接点作为新链表的头节点返回

// 时间复杂度：O(n * k),n是待排序元素的个数，k是数字位数
// 空间复杂度O(n + k)

const { LinkedList, ListNode } = require("../1. 链表基础/1. 建立线性链表")

function radixSort(head) {
    // 1. 计算最长的位数
    let size = 0
    let cur = head
    while (cur) {
        let len = String(cur.val).length
        if (len > size) {
            size = len
        }
        cur = cur.next
    }

    // 从个位到高位遍历位数
    for (let i = 0; i < size; i++) {
        let buckets = new Array(10).fill(0).map(_ => [])
        let cur = head
        while (cur) {
            // 以每个节点对应位上的数字为索引，将节点值存入对应的桶中
            buckets[Math.floor(cur.val / Math.pow(10, i)) % 10].push(cur.val)
            cur = cur.next
        }

        // 生成新的链表
        let dummy_head = new ListNode(-1)
        cur = dummy_head
        for (let j = 0; j < buckets.length; j++) {
            for (let k = 0; k < buckets[j].length; k++) {
                cur.next = new ListNode(buckets[j][k])  
                cur = cur.next
            }            
        }
        head = dummy_head.next
    }
    return head
}

let arr = [2, 7, 26, 25, 19, 17, 1, 90, 3, 36]
const linkList = new LinkedList(arr)
let res = radixSort(linkList.head)
console.log(res);